package com.sh.redis.suanfa;

import lombok.Data;

import java.util.Arrays;

/**
 * 二叉搜索树
 */
@Data
public class BinarySearchTree {
    private Node root;
    private static class Node {
        int element;//当前结点保存的元素
        Node left;//左结点
        Node right;//右结点
        Node parent;//父结点

        public Node(int element, Node parent) {
            this.element = element;
            this.parent = parent;
        }
    }

    public int compare(int i, Node m){
        if(i > m.element){
            return 1;
        }else if(i < m.element){
            return -1;
        }else{
            return 0;
        }
    }


    public void add(int i){
        // 如果不存在根节点，这个当做根节点
        if(root == null){
            root = new Node(i, null);
            return ;
        }

        Node node = root;
        Node parant = root;

        int flag = 0;
        while( node != null ){
            parant = node;
            flag = compare(i, parant);
            if(flag > 0){
                node = node.right;
            }else if(flag < 0){
                node = node.left;
            }else{
                node = null;
            }
        }

        Node newNode = new Node(i, parant);
        if(flag > 0){
            parant.right = newNode;
        }else{
            parant.left = newNode;
        }
    }

    /**
     * 删除节点
     */
    public void remove(Node removeNode){
        // 删除度为2的节点，需要找到该节点的后继节点，用后继节点来替换该节点的位置
        if(removeNode.left != null && removeNode.right != null){
            // 后继节点一定为叶子节点
            Node nextNode = findNextNode(removeNode);
            // 先断开叶子节点
            if(nextNode.parent.left == nextNode){
                nextNode.parent.left = null;
            }else{
                nextNode.parent.right = null;
            }
            if(removeNode.parent != null){
                if(removeNode.parent.left == removeNode){
                    removeNode.parent.left = nextNode;
                }else{
                    removeNode.parent.right = nextNode;
                }
            }else{
                // 父节点为空，表示为根节点
                root = nextNode;
            }

            nextNode.parent = removeNode.parent;
            nextNode.right = removeNode.right;
            nextNode.left = removeNode.left;

            removeNode.parent = null;
            removeNode.right = null;
            removeNode.left = null;
            return ;
        }

        // 删除度为1或者0的节点，是否为叶子节点，是否为根节点
        // 要删除的节点为根节点(先拿到要删除的节点的左孩子或者有孩子，因为上面考虑了双孩子的情况，这里只能拿到一个孩子，或者为null)
        Node temp = removeNode.left != null ? removeNode.left : removeNode.right;
        if(temp == null){
            // 如果没有孩子,即叶子节点
            if(removeNode.parent == null){
                // 并且没有父节点，那么该节点为整棵树，直接将root=null
                root = null;
            }else{
                // 如果有父节点，那么判断该节点是父节点的哪个孩子，将父节点对应的孩子赋值为null
                if(removeNode.parent.left == removeNode){
                    removeNode.parent.left = null;
                }else{
                    removeNode.parent.right = null;
                }
            }
        }else{
            // 如果不为叶子节点，
            if(removeNode.parent == null){
                if(removeNode.parent.left == removeNode){
                    removeNode.parent.left = temp;
                }else{
                    removeNode.parent.right = temp;
                }
            }else{
                root = temp;
            }
        }

    }


    /**
     * 找出前驱节点
     * @return
     */
    public static Node findPreNode(Node current){
        if(current.left != null){
            // 前置节点分为两种情况，一，前置节点在该节点的左子树上
            current = current.left;
            while(current.right != null){
                current = current.right;
            }
            return current;
        }else{
            // 二，前置节点在该节点的父节点或者祖父节点上(如果该节点没有左子树)
            while(current.parent != null && current.parent.left == current){
                current = current.parent;
            }
        }
        return current.parent;
    }


    /**
     * 找出后继节点
     * @return
     */
    public static Node findNextNode(Node current){
        if(current.right != null){
            // 前置节点分为两种情况，一，前置节点在该节点的右子树上
            current = current.right;
            while(current.left != null){
                current = current.left;
            }
            return current;
        }else{
            // 二，前置节点在该节点的父节点或者祖父节点上(如果该节点没有左子树)
            while(current.parent != null && current.parent.right == current){
                current = current.parent;
            }
        }
        return current.parent;
    }

    /**
     * 根据值找到并返回节点
     * @return
     */
    public Node findNode(int i){
        if(root == null){
            return null;
        }
        Node current = root;
        while(current.element != i){
            if(current.element > i){
                current = current.left;
            }else if(current.element < i){
                current = current.right;
            } else{
                return current;
            }
        }
        return current;
    }

    /**
     * 前序遍历
     */
    public static void qianxu(Node node){
        if(node == null){
            return ;
        }
        System.out.println(node.element);
        qianxu(node.left);
        qianxu(node.right);
    }

    /**
     * 中序遍历
     */
    public static void zhongxu(Node node){
        if(node == null){
            return ;
        }
        zhongxu(node.left);
        System.out.println(node.element);
        zhongxu(node.right);
    }

    /**
     * 后序遍历
     */
    public static void houxu(Node node){
        if(node == null){
            return ;
        }
        houxu(node.left);
        houxu(node.right);
        System.out.println(node.element);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{7,4,9,2,5,8,11,3,10,12};
        BinarySearchTree bst1 = new BinarySearchTree();
        //将数据添加到BST中
        Arrays.stream(arr).forEach(bst1::add);
        Node i = bst1.findNode(7);

        bst1.remove(i);
        zhongxu(bst1.root);

        System.out.println("--------------");
    }


}
